ICPC Live Archive/3928 - Ballroom lights/help/gomox.ar-pap-2010-d9b17e5cb110/tpc/needle-haystack/main.cpp

   1 #include <vector>
   2 #include <string>
   3 #include <iostream>
   4 #include <cassert>
   5 #include <cstdlib>
   6
   7 using namespace std;
   8
   9 typedef unsigned long long int lluint;
  10 typedef vector<int> vint;
  11
  12 #define forsn(i, s, n)  for (int i = (s); i < (n); i++)
  13 #define forn(i, n)      forsn (i, 0, n)
  14
  15 // Pre KMP
  16
  17 void pkmp(const string& s, vint& f) {
  18         int z = f[0] = -1;
  19         forsn (i, 1, s.size() + 1) {
  20                 while (z != -1 && s[i - 1] != s[z]) z = f[z];
  21                 f[i] = ++z; // z might be -1
  22         }
  23 }
  24
  25 // Buffer
  26
  27 #define TAMBUF  65536
  28 lluint pos;
  29 char buf[TAMBUF];
  30 int buf_size;
  31
  32 #define buf_sync() { \
  33         cin.getline(buf, TAMBUF + 1); \
  34         pos += buf_size; \
  35         buf_size = cin.gcount(); \
  36         cin.clear(); \
  37 }
  38
  39 #define buf_start() { \
  40         buf_sync(); \
  41         pos = 0; \
  42 }
  43
  44 // KMP
  45
  46 void kmp(const string& s, vint& f) {
  47         buf_start();
  48         const int final = s.size();
  49         int state = 0;
  50         while (true) {
  51                 forn (i, buf_size) {
  52                         if (state == final) {
  53                                 cout << (pos + i - final) << " ";
  54                         }
  55                         while (s[state] != buf[i]) {
  56                                 state = f[state];
  57                                 if (state == -1) break;
  58                         }
  59                         state++;
  60                 }
  61                 if (buf_size < TAMBUF) break;
  62                 buf_sync();
  63         }
  64 }
  65
  66 int main() {
  67         for (;;) {
  68                 int needle_size;
  69                 string needle;
  70                 cin >> needle_size;
  71                 if (cin.eof()) break;
  72                 cin >> needle;
  73                 assert(needle_size == needle.size());
  74                 cin.ignore(1);
  75
  76                 vint f(needle.size() + 1);
  77                 pkmp(needle, f);
  78                 kmp(needle, f);
  79                 cout << endl;
  80         }
  81         return 0;
  82 }
  83